def print_hi(name):
    print(f'Hi, {name}')


# ======================
# 王子川的归并排序实现（王子川_branch）
# 时间复杂度：O(n log n)
# 空间复杂度：O(n)
# ======================
def wzc_merge_sort(arr):
    """归并排序算法实现"""
    if len(arr) <= 1:
        return arr

    # 分割数组
    mid = len(arr) // 2
    left = wzc_merge_sort(arr[:mid])
    right = wzc_merge_sort(arr[mid:])

    # 合并排序后的子数组
    return merge(left, right)


def merge(left, right):
    merged = []
    l_idx = r_idx = 0

    # 合并两个有序数组
    while l_idx < len(left) and r_idx < len(right):
        if left[l_idx] < right[r_idx]:
            merged.append(left[l_idx])
            l_idx += 1
        else:
            merged.append(right[r_idx])
            r_idx += 1

    # 添加剩余元素
    merged.extend(left[l_idx:])
    merged.extend(right[r_idx:])
    return merged


if __name__ == '__main__':
    print_hi('PyCharm')

    # 测试排序算法
    test_arr = [38, 27, 43, 3, 9, 82, 10]
    print("原始数组：", test_arr)
    print("王子川排序结果：", wzc_merge_sort(test_arr))